package com.hsc.sreach;

/**
 * @author
 * @date 2025-06-03
 * @Description 约瑟夫环问题
 */
public class JosephRing {

    public static void main(String[] args) {
        JosephRing josephRing = new JosephRing();
        josephRing.josephRing2(11, 3);
    }


    /**
     * 思想：约瑟夫环问题 也是相当于查找元素
     * 1、在众多的人中 ，循环数数，数到3 的死掉
     * 举例：
     * 我们这有11个人，从头开始数数 ，如果数到3 这个人就死掉
     * 然后继续从0开始数数.
     * 在下面的例子中：
     * 1、从1开始数数  ，数到3 ，3这个人死掉
     * 2、继续从4开始 数 ，4为1 ，数到3 ，6这个人死掉
     * 3、继续从7开始数数 ，7、8、9，数到3 ，9这个人死掉
     * 4、继续从10 开始数数。10、11、1，数到3 ，1这个人死掉
     * 所以此时，已经死掉的 1、3、6、9，剩下的 2 、4、5、7、8、10、11
     * 这是第一轮报数结束，下一轮幸存者继续开始报数
     * 5、继续报数 ，从2 开始数数，2、4、5。数到3 ，5死掉
     * 6、从7 开始数数，7、8、10，数到3  ，10死掉
     * 7、从11 开始数数，11、2、4，数到3 ，4死掉
     * 8、从7开始数数，7、11、2 ，数到3 ，2死掉
     * 9、继续从7 开始数，7、8、11.数到3 。11死掉
     * 10、至此剩下的元素为 7、8，至此 ，到了这里死掉的 3、6、9、1、5、10、4、2、11
     * 剩下的两个为幸存者 ，最后他们数与不数已经不重要了，因为其他人都死掉了，没人知道
     * 11、但是他们还是继续数数 从7 开始数 7，8,7 所以7死掉了
     * 12 最后只剩下了 8没死
     *
     * @param playsCount 人数
     * @param luckNumber 幸运数字
     */
    public void josephRing1(int playsCount, int luckNumber) {
        // 创建一个数组 代表 有多少个玩家 ，他们只有两个状态 死与不死 我们使用true 与false  来进行表示
        boolean[] players = new boolean[playsCount];
        // 创建一个记录 记录现在数数 数到几了
        int count = 0;
        // 创建一个记录 表示死掉的玩家数量
        int dealCount = 0;

        // 对给的玩家数量进行从0开始数数 所以我们可以使用一个循环表示
        for (int i = 0; i < playsCount; i++) {
            // 开始报数
            count++;
            // 如果 数到luckNumber了 数到幸运数字了 这个人就死掉
            if (count == luckNumber) {
                // 这个人死掉 我们将当前的这个状态置为true 表示死掉 了
                players[i] = true;
                System.out.println("第" + (i + 1) + "个玩家死掉了");
                // 需要让计数器重新进行计数
                count = 0;
                dealCount++;// 记录死掉的人数
            }
            // 到了这里 只是说一轮的数数进行结束了 还需要进行下一轮的数数
            // 但是我们不知道到底要循环多少次 所以我们使用while循环
        }
    }

    /**
     * 思想：约瑟夫环问题
     * 1、在众多的人中 ，循环数数，数到3 的死掉
     * 举例：
     * 我们这有12个人，从头开始数数 ，如果数到3 这个人就死掉
     * 然后继续从0开始数数.
     * 在下面的例子中：
     * 1、从1开始数数  ，数到3 ，3这个人死掉
     * 2、继续从4开始 数 ，4为1 ，数到3 ，6这个人死掉
     * 3、继续从7开始数数 ，7、8、9，数到3 ，9这个人死掉
     * 4、继续从10 开始数数。10、11、1，数到3 ，1这个人死掉
     * 所以此时，已经死掉的 1、3、6、9，剩下的 2 、4、5、7、8、10、11
     * 这是第一轮报数结束，下一轮幸存者继续开始报数
     * 5、继续报数 ，从2 开始数数，2、4、5。数到3 ，5死掉
     * 6、从7 开始数数，7、8、10，数到3  ，10死掉
     * 7、从11 开始数数，11、2、4，数到3 ，4死掉
     * 8、从7开始数数，7、11、2 ，数到3 ，2死掉
     * 9、继续从7 开始数，7、8、11.数到3 。11死掉
     * 10、至此剩下的元素为 7、8，至此 ，到了这里死掉的 3、6、9、1、5、10、4、2、11
     * 剩下的两个为幸存者 ，最后他们数与不数已经不重要了，因为其他人都死掉了，没人知道
     * 11、但是他们还是继续数数 从7 开始数 7，8,7 所以7死掉了
     * 12 最后只剩下了 8没死
     *
     * @param playsCount 人数
     * @param luckNumber 幸运数字
     */
    public void josephRing2(int playsCount, int luckNumber) {
        // 创建一个数组 代表 有多少个玩家 ，他们只有两个状态 死与不死 我们使用true 与false  来进行表示
        boolean[] players = new boolean[playsCount];
        // 创建一个记录 记录现在数数 数到几了
        int count = 0;
        // 创建一个记录 表示死掉的玩家数量
        int dealCount = 0;
        // 使用 标记标记 循环 while
        over:
        while (true) { // 控制轮次 因为不知道 要循环多少次 所以索性使用死循环
            System.out.println("新的一轮比较开始");
            // 对给的玩家数量进行从0开始数数 所以我们可以使用一个循环表示
            for (int i = 0; i < playsCount; i++) {
                // 这里为什么需要判断呢？
                // 因为新的额 一轮比较 开始 那些已经死掉的 玩家 不需要再进行数数了 所以直接进行跳过 下一个没死的玩家接着数数
                if (players[i] == true) {
                    continue;
                }
                // 开始报数 新的一轮开始数数 这个count 是继续接着的
                count++;
                // 如果 数到luckNumber了 数到幸运数字了 这个人就死掉
                if (count == luckNumber) {
                    // 这个人死掉 我们将当前的这个状态置为true 表示死掉 了
                    players[i] = true;
                    System.out.println("第" + (i + 1) + "个玩家死掉了");
                    // 需要让计数器重新进行计数
                    count = 0;
                    dealCount++;// 记录死掉的人数
                    // 到了这里 只是说一轮的数数进行结束了 还需要进行下一轮的数数
                    // 但是我们不知道到底要循环多少次 所以我们使用while循环
                    // 循环的终止条件是什么呢？ --就是死掉的人数 =  玩家数量 循环将会跳出
                    // 但是我们需要跳出的外层的循环 用来控制不同的圈数的 我们可以使用循环标记 进行

                    // 如果死的人数 跟玩家的数量一样 我们就跳出整个循环
                    if (dealCount == playsCount) {
                        break over;
                    }
                }

            }
        }

    }
}
